one-way function

Definition

A function $f : \{0,1\}^* \to \{0,1\}^*$ is a one-way function if:

• $f$ can be computed in polynomial time
• $\forall$ PPT adversaries $A$:
  • $\Pr[f(x')=y : x \gets \{0,1\}^n, y = f(x), x' \gets A(1^n,y)] = \mathsf{negl}(n)$
    • (negligible function)

(intuitively: $f$ easy to evaluate, hard to invert, meaning hard to find preimage of given $y= f(x)$)

Notes

• Goldreich-Levin theorem
• $f$ doesn't have to be one-to-one
• special case of bijective $f$ is one-way permutation
• existence of one-way functions would imply P≠NP

References

1. https://www.khoury.northeastern.edu/home/wichs/class/crypto-fall17/lecture7.pdf
2. https://www.cs.purdue.edu/homes/hmaji/teaching/Fall 2017/lectures/19.pdf
3. https://github.com/cpeikert/TheoryOfCryptography/blob/master/lec02 - Computational Hardness.pdf
4. https://en.wikipedia.org/wiki/One-way_function